#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <condition_variable>
#include <mutex>
#include <queue>
#include <optional>

// 6.9: 使用原子指令实现互斥锁 (两种方式：test_and_set 与 compare_exchange)

struct TASLock {
    std::atomic<int> available{0}; // 0: free, 1: locked

    void init() { available.store(0, std::memory_order_relaxed); }

    void acquire() {
        // emulate test_and_set via atomic exchange
        while (true) {
            int old = available.exchange(1, std::memory_order_acquire);
            if (old == 0) break; // acquired
            std::this_thread::yield();
        }
    }

    void release() {
        available.store(0, std::memory_order_release);
    }
};

struct CASLock {
    std::atomic<int> available{0}; // 0: free, 1: locked

    void init() { available.store(0, std::memory_order_relaxed); }

    void acquire() {
        int expected;
        while (true) {
            expected = 0;
            if (available.compare_exchange_weak(expected, 1, std::memory_order_acquire)) {
                break; // acquired
            }
            std::this_thread::yield();
        }
    }

    void release() {
        available.store(0, std::memory_order_release);
    }
};

int main() {
    const int threads = 4;
    const int iterations = 100000;

    // Test TASLock
    TASLock tas;
    tas.init();
    int counter_tas = 0;
    std::vector<std::thread> v1;
    v1.reserve(threads);
    for (int i = 0; i < threads; ++i) {
        v1.emplace_back([&]() {
            for (int k = 0; k < iterations; ++k) {
                tas.acquire();
                ++counter_tas;
                tas.release();
            }
        });
    }
    for (auto& t : v1) t.join();
    std::cout << "TASLock counter: " << counter_tas << std::endl;

    // Test CASLock
    CASLock cas;
    cas.init();
    int counter_cas = 0;
    std::vector<std::thread> v2;
    v2.reserve(threads);
    for (int i = 0; i < threads; ++i) {
        v2.emplace_back([&]() {
            for (int k = 0; k < iterations; ++k) {
                cas.acquire();
                ++counter_cas;
                cas.release();
            }
        });
    }
    for (auto& t : v2) t.join();
    std::cout << "CASLock counter: " << counter_cas << std::endl;

    return 0;
}